package com.datastructure.test.findlowestcommonancestor;

import com.datastructure.test.LowestCommonAncestor.LowestCommonAncestor;
import com.datastructure.test.stringsummary.StringSummary;

import java.util.Iterator;
import java.util.Stack;

public class FindLowestCommonAncestor {

    public static void main(String[] args) {
        TreeNode treeNode = new TreeNode(3);
        treeNode.left = new TreeNode(5);
        treeNode.right = new TreeNode(1);
        treeNode.left.left=new TreeNode(6);
        treeNode.left.right=new TreeNode(2);
        treeNode.right.left=new TreeNode(0);
        treeNode.right.right=new TreeNode(8);
        treeNode.left.right.left=new TreeNode(7);
        treeNode.left.right.right=new TreeNode(4);
        FindLowestCommonAncestor findLowestCommonAncestor = new FindLowestCommonAncestor();
        int i = findLowestCommonAncestor.lowestCommonAncestor(treeNode, 5, 1);
        System.out.println(i);
    }

    public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
        // write code here
        Stack<TreeNode> stackLeft = new Stack<>();
        Stack<TreeNode> stackRight = new Stack<>();
        insertStack(root,o1,stackLeft);
        insertStack(root,o2,stackRight);
        int father = root.val;
        while (!(stackLeft.isEmpty()||stackRight.isEmpty())){
            int left = stackLeft.pop().val;
            int right = stackRight.pop().val;
            if(left==right){
                 father = left;
            }else {
                break;
            }
        }
        return father;
    }

    private boolean insertStack(TreeNode root, int o1, Stack<TreeNode> stack) {
        if(root==null){
            return false;
        }
        if(root.val==o1||insertStack(root.left,o1,stack)
                ||insertStack(root.right,o1,stack)){
            stack.push(root);
            System.out.print(root.val+" ");
            return true;
        }else {
            return false;
        }
    }

    boolean getPath(TreeNode root, int target, Stack<TreeNode> pathStack){
        if(root==null)return false;
        if(root.val==target//重点在于这个三合一的判定条件
                ||getPath(root.left,target,pathStack)
                ||getPath(root.right,target,pathStack)){
            System.out.print(root.val+" ");
            pathStack.push(root);
            return true;
        }
        return false;
    }
}

class TreeNode {
   int val = 0;
   TreeNode left = null;
   TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;
    }
}
